1. Field of the Invention
The invention relates to flash memories, and more particularly to conversion between logical addresses and physical addresses of flash memories.
2. Description of the Related Art
A flash memory is a non-volatile memory that can be electrically erased and reprogrammed. Flash memories are primarily used in memory cards and USB flash drives for general storage and transfer of data between computers and other digital products. A flash memory costs far less than an EEPROM and therefore has become a dominant memory device applied in electronic products. Examples of devices applying flash memories include Personal Digital Assistants (PDA) and laptop computers, digital audio players, digital cameras and mobile phones.
A host ordinarily uses a flash storage device for data storage. A conventional flash storage device, such as a memory card, comprises a controller and at least one flash memory. When a host wants to store data in a flash storage device, the host sends address and data to be stored in the address to the flash storage device. The address sent by the host for storing data is referred to as a logical address, and addresses used by a flash memory are referred to as physical addresses. Because the logical address has a different format from that of the physical addresses, a controller of the flash storage device must first convert the logical address received from the host to a physical address, so that the flash memory of the flash storage device can store data according to the physical address. When a host wants to read data from the flash storage device, the host sends a logical address where data is to be read to the flash storage device. A controller of the flash storage device then converts the logical address to a physical address, so that the flash memory of the flash storage device can read data from the physical address, and the read-out data can be sent back to the host.
Because a controller of a flash storage device must convert logical addresses to physical addresses, the controller ordinarily has a link table for storing a mapping relationship between logical addresses and physical addresses. The controller can then perform address conversion according to the mapping relationship stored in the link table. The link table must record a mapping relationship for all physical addresses of a flash memory. When data capacity of the flash memory is greater, the data amount of the mapping relationship stored in the link table is also greater. The link table is ordinarily stored in the flash memory. After the flash storage device is enabled, the link table is loaded from the flash memory to a memory of a controller. Whenever the controller writes data to the flash memory, the mapping relationship of the link table stored in the memory of the controller is changed. If the host accesses data stored in the flash storage device at a high frequency, then the workload required by the controller for maintaining the link table increases. Thus, the data access process between the host and the flash storage device may be delayed. Accordingly, a method for improving the efficiency of managing a link table for a controller of a flash storage device is required.